package com.jxb.test20241216;

import com.jxb.first.ListNode;

import java.util.HashMap;
import java.util.Map;

public class IntersectionTwoLinkedLists_160 {

    public static void main(String[] args) {

    }

    //暴力破解
    public static ListNode baoLi(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        while (headA.next != null) {
            while (headB.next != null) {
                if (headA.val == headB.val) {
                    return headA;
                }
                headA = headA.next;
            }
            headB = headB.next;
        }
        return null;
    }

    //hash
    public static ListNode hash(ListNode headA, ListNode headB) {
        Map<Integer,ListNode> map = new HashMap<>();
        while (headA.next != null) {
            map.put(headA.val,headA);
            headA = headA.next;
        }

        while (headB.next != null) {
            if (map.containsKey(headB.val)) {
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }

    //双指针
    public static ListNode DuPa(ListNode headA, ListNode headB) {
        ListNode p1 = headA;
        ListNode p2 = headB;
        while (p1 != p2) {
            p1 = p1.next == null ? headB:p1.next;
            p2 = p2.next == null ? headA:p2.next;
        }
        return p1;
    }

    //计算2个链表的长度差
    public static ListNode diff(ListNode headA, ListNode headB) {
        ListNode aln = headA;
        ListNode bln = headB;
        int aL = 0;
        int bL = 0;
        while (aln.next != null) {
            aL++;
            aln = aln.next;
        }
        while (bln.next != null) {
            bL++;
            bln = bln.next;
        }

        int diff = 0;
        if (aL > bL) {
            diff = aL - bL;
            aln = headA;
            while (diff > 0) {
                aln = aln.next;
            }
        }
        if (bL > aL) {
            diff = bL - aL;
            bln = headB;
            while (diff > 0) {
                bln = bln.next;
            }
        }

        while (aln.next != null && bln.next != null) {
            if (aln.val == bln.val) {
                return aln;
            }
            aln = aln.next;
            bln = bln.next;
        }
        return null;
    }



}
